package collections;

import java.util.Arrays;

import util.Heap;


public class PriorityQueueMax<T extends Comparable<T>> {
	private Comparable<T>[] items;
	private int available;

	@SuppressWarnings("unchecked")
	public PriorityQueueMax() {
		items = new Comparable[1];
		available = 0;
	}
	
	public int getAvailable() {
		return available;
	}

	@SuppressWarnings("unchecked")
	public T maximum()
	{
		return (T)items[0];
	}
	@SuppressWarnings("unchecked")
	public T extractMax() throws Exception
	{
		if(available == 0)
			throw new Exception("heap underflow");
		
		T v = (T)items[0];
		items[0] = items[-- available];
		Heap.maxHeapify(items, 0, available);
		return v;
	}

	@SuppressWarnings("unchecked")
	public void insert(T newValue) throws Exception
	{
		if(available == items.length)
		{
			Comparable<T>[] newItems = new Comparable[items.length << 1];
			System.arraycopy(items, 0, newItems, 0, available);
			items = newItems;
		}
		
		items[available ++ ] = newValue;
		int newIndex = available - 1;
		int parent;
		T parentValue;
		while((parent = Heap.parent(newIndex)) >= 0 && (parentValue = (T)items[parent]).compareTo(newValue) < 0)
		{
			items[newIndex] = parentValue;
			newIndex = parent;
		}
		
		items[newIndex] = newValue;
	}
	
	public void delete(int i) throws Exception
	{
		validateIndex(i);
		items[i] = items[-- available];
		Heap.maxHeapify(items, i, available);
	}
	
	private void validateIndex(int index) throws Exception
	{
		if(index < 0 || index >= available)
			throw new Exception("invailable index");
	}
	
	public static void main(String[] args) throws Exception {
		PriorityQueueMax<Integer> queue = new PriorityQueueMax<Integer>();

		queue.insert(1);
		queue.insert(100);
		queue.insert(99);
		queue.insert(22);
		queue.insert(1011);
		queue.insert(10);
		queue.insert(8);
		queue.insert(78);
		
		System.out.println("删除前:" + Arrays.toString(queue.items));
		queue.delete(2);
		System.out.println("删除后:" + Arrays.toString(queue.items));

		while(queue.getAvailable() > 0)
		{
			System.out.println(queue.extractMax());
		}
	}
}
